Optimal online assignment with forecasts.
We study a class of online assignment problems that naturally generalizes problems such as online bipartite matching, allocation, and budgeted bidders, in which we wish to minimize the value of some convex objective function subject to a set of linear supply and demand constraints. Motivated by real world conditions where the online input is often far from worst-case, we formulate the online assignment with forecast problem. In this model, we assume to have access to random samples from the future set of arriving vertices. We propose a novel use of the dual space for convex optimization problems. By working in the subspace of the dual space, we are able to describe the optimal primal solution implicitly in space proportional to the demand side of the input graph. More importantly, we prove that representing the primal solution using such a compact allocation plan yields a robust online algorithm which is able to make near-optimal online decisions, generalizing the solution even to unsampled (and previously unseen) input.
Finding the Jaccard Median.

Efficiently evaluating complex boolean expressions.

Finding the Jaccard Median.

A Model of Computation for MapReduce.

Generalized distances between rankings.

Inventory Allocation for Online Graphical Display Advertising

Similarity caching.
Future parallel computers must efficiently execute not only hand-coded applications but also programs written in high-level, parallel programming languages. Today’s machines limit these programs to a single communication paradigm, either message-passing or shared-memory, which results in uneven performance. This paper addresses this problem by defining an interface, Tempest, that exposes low-level communication and memory-system mechanisms so programmers and compilers can customize policies for a given application. Typhoon is a proposed hardware platform that implements these mechanisms with a fully-programmable, user-level processor in the network interface. We demonstrate the utility of Tempest with two examples. First, the Stache protocol uses Tempest’s finegrain access control mechanisms to manage part of a processor’s local memory as a large, fully-associative cache for remote data. We simulated Typhoon on the Wisconsin Wind Tunnel and found that Stache running on Typhoon performs comparably (±30%) to an all-hardware Dir N NB cache-coherence protocol for five shared-memory programs. Second, we illustrate how programmers or compilers can use Tempest’s flexibility to exploit an application’s sharing patterns with a custom protocol. For the EM3D application, the custom protocol improves performance up to 35 % over the all-hardware protocol.
Getting recommender systems to think outside the box.

Bidding for Representative Allocations for Display Advertising.

Social Networks and Stable Matchings in the Job Market.

Top%2Dk aggregation using intersections of ranked inputs.
There has been considerable past work on efficiently computing top k objects by aggregating information from multiple ranked lists of these objects. An important instance of this problem is query processing in search engines: One has to combine information from several different posting lists (rankings) of web pages (objects) to obtain the top k web pages to answer user queries. Two particularly well-studied approaches to achieve efficiency in top-k aggregation include early-termination algorithms (e.g., TA and NRA) and preaggregation of some of the input lists. However, there has been little work on a rigorous treatment of combining these approaches. We generalize the TA and NRA algorithms to the case when preaggregated intersection lists are available in addition to the original lists. We show that our versions of TA and NRA continue to remain “instance optimal, ” a very strong optimality notion that is a highlight of the original TA and NRA algorithms. Using an index of millions of web pages and real-world search engine queries, we empirically characterize the performance gains offered by our new algorithms. We show that the practical benefits of intersection lists can be fully realized only with an early-termination algorithm.
Adaptive bidding for display advertising.

Nearest%2Dneighbor caching for content%2Dmatch applications.



Social Networks and Stable Matchings in the Job Market

Battling Predictability and Overconcentration in Recommender Systems.
Today’s recommendation systems have evolved far beyond the initial approaches from more than a decade ago, and have seen a great deal of commercial success (c.f., Amazon and Netflix). However, they are still far from perfect, and face tremendous challenges in increasing the overall utility of the recommendations. These challenges are present in all stages of the recommendation process. They begin with the cold start problem:
Worst%2DCase and Smoothed Analysis of the ICP Algorithm

Indexing Boolean Expressions.
We consider the problem of efficiently indexing Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF) Boolean expressions over a high-dimensional multi-valued attribute space. The goal is to rapidly find the set of Boolean expressions that evaluate to true for a given assignment of values to attributes. A solution to this problem has applications in online advertising (where a Boolean expression represents an advertiser’s user targeting requirements, and an assignment of values to attributes represents the characteristics of a user visiting an online page) and in general any publish/subscribe system (where a Boolean expression represents a subscription, and an assignment of values to attributes represents an event). All existing solutions that we are aware of can only index a specialized sub-set of conjunctive and/or disjunctive expressions, and cannot efficiently handle general DNF and CNF expressions (including NOTs) over multi-valued attributes. In this paper, we present a novel solution based on the inverted list data structure that enables us to index arbitrarily complex DNF and CNF Boolean expressions over multi-valued attributes. An interesting aspect of our solution is that, by virtue of leveraging inverted lists traditionally used for ranked information retrieval, we can efficiently return the top-N matching Boolean expressions. This capability enables emerging applications such as ranked publish/subscribe systems [16], where only the top subscriptions that match an event are desired. For example, in online advertising there is a limit on the number of advertisements that can be shown on a given page and only the “best ” advertisements can be displayed. We have evaluated our proposed technique based on data from an online advertising application, and the results show a dramatic performance improvement over prior techniques. 1.
Worst%2DCase and Smoothed Analysis of the ICP Algorithm



Optimal envy%2Dfree pricing with metric substitutability.

The hiring problem and Lake Wobegon strategies.
We introduce the hiring problem, in which a growing company continuously interviews and decides whether to hire applicants. This problem is similar in spirit but quite different from the well-studied secretary problem. Like the secretary problem, it captures fundamental aspects of decision making under uncertainty and has many possible applications. We analyze natural strategies of hiring above the current average, considering both the mean and the median averages; we call these Lake Wobegon strategies. Like the hiring problem itself, our strategies are intuitive, simple to describe, and amenable to mathematically and economically significant modifications. We demonstrate several intriguing behaviors of the two strategies. Specifically, we show dramatic differences between hiring above the mean and above the median. We also show that both strategies are intrinsically connected to the lognormal distribution, leading to only very weak concentration results, and the marked importance of the first few hires on the overall outcome. 1
Relaxation in text search using taxonomies.
In this paper we propose a novel document retrieval model in which text queries are augmented with multi-dimensional taxonomy restrictions. These restrictions may be relaxed at a cost to result quality. This new model may be applicable in many arenas, including multifaceted, product, and local search, where documents are augmented with hierarchical metadata such as topic or location. We present efficient algorithms for indexing and query processing in this new retrieval model. We decompose query processing into two sub-problems: first, an online search problem to determine the correct overall level of relaxation cost that must be incurred to generate the top k results; and second, a budgeted relaxation search problem in which all results at a particular relaxation cost must be produced at minimal cost. We show the latter problem is solvable exactly in two hierarchical dimensions, is NP-hard in three or more dimensions, but admits efficient approximation algorithms with provable guarantees. We present experimental results evaluating our algorithms on both synthetic and real data, showing order of magnitude improvements over the baseline algorithm. 1.
Sponsored Search Auctions with Reserve Prices Going Beyond Separability.

Relaxation in text search using taxonomies.
In this paper we propose a novel document retrieval model in which text queries are augmented with multi-dimensional taxonomy restrictions. These restrictions may be relaxed at a cost to result quality. This new model may be applicable in many arenas, including multifaceted, product, and local search, where documents are augmented with hierarchical metadata such as topic or location. We present efficient algorithms for indexing and query processing in this new retrieval model. We decompose query processing into two sub-problems: first, an online search problem to determine the correct overall level of relaxation cost that must be incurred to generate the top k results; and second, a budgeted relaxation search problem in which all results at a particular relaxation cost must be produced at minimal cost. We show the latter problem is solvable exactly in two hierarchical dimensions, is NP-hard in three or more dimensions, but admits efficient approximation algorithms with provable guarantees. We present experimental results evaluating our algorithms on both synthetic and real data, showing order of magnitude improvements over the baseline algorithm. 1.
On threshold behavior in query incentive networks.

Tracing the Path New Model and Algorithms for Collaborative Filtering.

k%2Dmeans   the advantages of careful seeding.
in co-operation with
Worst%2Dcase and Smoothed Analysis of the ICP Algorithm

Using web%2Dgraph distance for relevance feedback in web search.
We study the effect of user supplied relevance feedback in improving web search results. Rather than using query refinement or document similarity measures to rerank results, we show that the web-graph distance between two documents is a robust measure of their relative relevancy. We demonstrate how the use of this metric can improve the rankings of result URLs, even when the user only rates one document in the dataset. Our research suggests that such interactive systems can significantly improve search results.
Efficiently computing succinct trade%2Doff curves.
Abstract. Trade-off (aka Pareto) curves are typically used to represent the trade-off among different objectives in multiobjective optimization problems. Although trade-off curves are exponentially large for typical combinatorial optimization problems (and infinite for continuous problems), it was observed in [PY1] that there exist polynomial size ɛ approximations for any ɛ&gt; 0, and that under certain general conditions, such approximate ɛ-Pareto curves can be constructed in polynomial time. In this paper we seek general-purpose algorithms for the efficient approximation of trade-off curves using as few points as possible. In the case of two objectives, we present a general algorithm that efficiently computes an ɛ-Pareto curve that uses at most 3 times the number of points of the smallest such curve; we show that no algorithm can be better than 3-competitive in this setting. If we relax ɛ to any ɛ ′&gt; ɛ, then we can efficeintly construct an ɛ ′-curve that uses no more points than the smallest ɛ-curve. With three objectives we show that no algorithm can be c-competitive for any constant c unless it is allowed to use a larger ɛ value. We present an algorithm that is 4-competitive for any ɛ ′&gt; (1 + ɛ) 2 − 1. We explore the problem in high dimensions and give hardness proofs showing that (unless P=NP) no constant approximation factor can be achieved efficiently even if we relax ɛ by an arbitrary constant. 1
How slow is the k%2Dmeans method%3F

Efficiently computing succinct trade%2Doff curves.
Abstract. Trade-off (aka Pareto) curves are typically used to represent the trade-off among different objectives in multiobjective optimization problems. Although trade-off curves are exponentially large for typical combinatorial optimization problems (and infinite for continuous problems), it was observed in [PY1] that there exist polynomial size ɛ approximations for any ɛ&gt; 0, and that under certain general conditions, such approximate ɛ-Pareto curves can be constructed in polynomial time. In this paper we seek general-purpose algorithms for the efficient approximation of trade-off curves using as few points as possible. In the case of two objectives, we present a general algorithm that efficiently computes an ɛ-Pareto curve that uses at most 3 times the number of points of the smallest such curve; we show that no algorithm can be better than 3-competitive in this setting. If we relax ɛ to any ɛ ′&gt; ɛ, then we can efficeintly construct an ɛ ′-curve that uses no more points than the smallest ɛ-curve. With three objectives we show that no algorithm can be c-competitive for any constant c unless it is allowed to use a larger ɛ value. We present an algorithm that is 4-competitive for any ɛ ′&gt; (1 + ɛ) 2 − 1. We explore the problem in high dimensions and give hardness proofs showing that (unless P=NP) no constant approximation factor can be achieved efficiently even if we relax ɛ by an arbitrary constant. 1
Efficiently Computing Succinct Trade%2DOff Curves.
Abstract. Trade-off (aka Pareto) curves are typically used to represent the trade-off among different objectives in multiobjective optimization problems. Although trade-off curves are exponentially large for typical combinatorial optimization problems (and infinite for continuous problems), it was observed in [PY1] that there exist polynomial size ɛ approximations for any ɛ&gt; 0, and that under certain general conditions, such approximate ɛ-Pareto curves can be constructed in polynomial time. In this paper we seek general-purpose algorithms for the efficient approximation of trade-off curves using as few points as possible. In the case of two objectives, we present a general algorithm that efficiently computes an ɛ-Pareto curve that uses at most 3 times the number of points of the smallest such curve; we show that no algorithm can be better than 3-competitive in this setting. If we relax ɛ to any ɛ ′&gt; ɛ, then we can efficeintly construct an ɛ ′-curve that uses no more points than the smallest ɛ-curve. With three objectives we show that no algorithm can be c-competitive for any constant c unless it is allowed to use a larger ɛ value. We present an algorithm that is 4-competitive for any ɛ ′&gt; (1 + ɛ) 2 − 1. We explore the problem in high dimensions and give hardness proofs showing that (unless P=NP) no constant approximation factor can be achieved efficiently even if we relax ɛ by an arbitrary constant. 1
A Complete
A universal algorithm for sequential data compression is presented. Its performance is investigated with respect to a nonprobabilistic model of constrained sources. The compression ratio achieved by the proposed universal code uniformly approaches the lower bounds on the compression ratios attainable by block-to-variable codes and variable-to-block codes designed to match a completely specified source.
On the General Reconfiguration Problem for Expanding Cube Style Modular Robots.

